// pathIntegrityChecker.ts

/**
 * 航班传输接口
 */
export interface Transport {
  fromCity: string;
  arivCity: string;
}

/**
 * 路径检查结果接口
 */
export interface PathCheckResult {
  isComplete: boolean;
  path?: string[]; // 可选：完整的路径城市列表
}

/**
 * 检查路径完整性的主要函数
 * @param startCity 出发城市
 * @param endCity 目的城市
 * @param transports 航班列表
 * @returns 路径检查结果
 */
export function checkPathIntegrity(
  startCity: string, 
  endCity: string, 
  transports: Transport[]
): PathCheckResult {
  // 如果起点和终点相同
  if (startCity === endCity) {
    return {
      isComplete: true,
      path: [startCity]
    };
  }

  // 如果没有航班信息
  if (transports.length === 0) {
    return {
      isComplete: false,
      path: []
    };
  }

  // 构建图结构 - 邻接表
  const graph: Record<string, string[]> = {};
  transports.forEach(transport => {
    if (!graph[transport.fromCity]) {
      graph[transport.fromCity] = [];
    }
    graph[transport.fromCity].push(transport.arivCity);
  });

  // 使用BFS查找路径
  const visited = new Set<string>();
  const queue: string[] = [startCity];
  const prev: Record<string, string | null> = { [startCity]: null };
  
  visited.add(startCity);
  let found = false;

  while (queue.length > 0) {
    const current = queue.shift()!;
    
    if (current === endCity) {
      found = true;
      break;
    }
    
    // 检查当前城市是否有出站航班
    if (graph[current]) {
      for (const neighbor of graph[current]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          prev[neighbor] = current;
          queue.push(neighbor);
        }
      }
    }
  }

  // 如果找到了路径
  if (found) {
    const path = reconstructPath(prev, endCity);
    return {
      isComplete: true,
      path
    };
  }

  
  return {
    isComplete: false,
    path: Array.from(visited) // 返回已访问的城市（可达部分）
  };
}

/**
 * 从前置节点字典重建完整路径
 * @param prev 前置节点字典
 * @param endCity 终点城市
 * @returns 完整的路径数组
 */
function reconstructPath(prev: Record<string, string | null>, endCity: string): string[] {
  const path: string[] = [];
  let current: string | null = endCity;
  
  while (current !== null) {
    path.unshift(current);
    current = prev[current];
  }
  
  return path;
}

/**
 * 验证城市选择是否有效
 * @param startCity 出发城市
 * @param endCity 目的城市
 * @param availableCities 可用城市列表
 * @returns 错误消息或null（如果有效）
 */
export function validateCitySelection(
    startCity: string,
    endCity: string,
    availableCities: string[]
): string | null {
  if (!startCity) return '请选择出发城市';
  if (!endCity) return '请选择目的城市';
  if (startCity === endCity) return '出发城市和目的城市不能相同';
  if (!availableCities.includes(startCity)) return '出发城市不在可用城市列表中';
  if (!availableCities.includes(endCity)) return '目的城市不在可用城市列表中';
  return null;
}
